import math


class SelectSort:
    @staticmethod
    def sort(l: list):
        for i in range(len(l)):
            mini_index = i

            for j in range(i, len(l)):
                if l[j] < l[mini_index]:
                    mini_index = j
            SelectSort._exchange(l, i, mini_index)

    @staticmethod
    def _exchange(arr: list, a: int, b: int):
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp


class InsertSort:
    @staticmethod
    def sort(l: list):
        for i in range(1, len(l)):
            a = l[i]
            j = i
            while j > 0 and a < l[j - 1]:
                l[j] = l[j - 1]
                j -= 1
            l[j] = a


class MergeSort:
    @staticmethod
    def sort(array: list):
        MergeSort._sort_by_recursion(array, 0, len(array) - 1)

    @staticmethod
    def _sort_by_recursion(array: list, l: int, r: int):
        if l >= r:
            return
        mid = l + math.floor((r - l) / 2)
        MergeSort._sort_by_recursion(array, l, mid)
        MergeSort._sort_by_recursion(array, mid + 1, r)
        if array[mid] > array[mid + 1]:
            MergeSort._merge(array, l, mid, r)

    @classmethod
    def sort_from_below(cls, array: list):
        step = 1
        length = len(array)
        while step < length:
            left = 0
            while left + step < length:

                right = min(length - 1, left + step * 2 - 1)
                mid = left + step - 1
                if array[mid] > array[mid + 1]:
                    cls._merge(array, left, mid, right)
                left += step * 2
            step *= 2

    @staticmethod
    def _get_r(length: int, i: int, step: int) -> int:
        if i + step - 1 >= length:
            return length - 1
        else:
            return i + step - 1

    @staticmethod
    def _merge(array: list, l: int, mid: int, r: int):
        temp = array[l:r + 1]

        n = l
        i = l
        j = mid + 1
        while n <= r:
            if i > mid:
                array[n] = temp[j - l]
                j += 1
            elif j > r:
                array[n] = temp[i - l]
                i += 1
            elif temp[i - l] <= temp[j - l]:
                array[n] = temp[i - l]
                i += 1
            elif temp[i - l] > temp[j - l]:
                array[n] = temp[j - l]
                j += 1
            n += 1


class QuickSort:
    @staticmethod
    def sort(arr: list):
        QuickSort._sort_by_recursion(arr, 0, len(arr) - 1)

    @staticmethod
    def sort_three_ways(arr: list):
        QuickSort._sort_by_recursion_three_ways(arr, 0, len(arr) - 1)

    @staticmethod
    def _sort_by_recursion(arr: list, left: int, right: int):
        if left >= right:
            return
        j = QuickSort._partition(arr, left, right)
        QuickSort._sort_by_recursion(arr, left, j - 1)
        QuickSort._sort_by_recursion(arr, j + 1, right)

    @staticmethod
    def _sort_by_recursion_three_ways(arr: list, left: int, right: int):
        if left >= right:
            return
        lt, gt = QuickSort._partition_three_ways(arr, left, right)
        QuickSort._sort_by_recursion_three_ways(arr, left, lt - 1)
        QuickSort._sort_by_recursion_three_ways(arr, gt, right)

    @staticmethod
    def _partition(arr: list, left: int, right: int):
        # 随机取一个数放最开头作为中间值
        QuickSort._random_v(arr, left, right)

        v = arr[left]
        j = left
        i = left + 1
        while i <= right:
            if arr[i] < v:
                j += 1
                QuickSort._exchange(arr, i, j)
            i += 1
        QuickSort._exchange(arr, left, j)
        return j

    @staticmethod
    def _partition_three_ways(arr: list, left: int, right: int):
        # 随机取一个数放最开头作为中间值
        QuickSort._random_v(arr, left, right)

        # arr[left+1...less_than]<v arr[less_than+1...i-1]==v  arr[great_than...right]>v
        v = arr[left]
        i = left + 1
        less_than = left
        great_than = right + 1
        while i < great_than:
            if arr[i] < v:
                less_than += 1
                QuickSort._exchange(arr, i, less_than)
                i += 1
            elif arr[i] == v:
                i += 1
            elif arr[i] > v:
                great_than -= 1
                QuickSort._exchange(arr, i, great_than)
        QuickSort._exchange(arr, less_than, left)

        # arr[left...less_than-1]<v arr[less_than...great_than-1]==v  arr[great_than...right]>v
        return less_than, great_than

    @staticmethod
    def _exchange(arr: list, a: int, b: int):
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp

    @staticmethod
    def _random_v(arr: list, left: int, right: int):
        from random import randint
        p = randint(0, right - left) + left
        QuickSort._exchange(arr, p, left)


class BubbleSort:
    @staticmethod
    def sort(arr: list):
        count = len(arr)
        # arr[count - i, count) 是排好序的
        i = 0
        while i < count:
            # # 如果一次循环中一次都没交换说明当前数组是从小到大有序的了
            # un_exchanges = True

            # 记录最后一次交换的index,后面因为都没交换说明后面是有序的
            last_swapped_index = 0
            for j in range(0, count - i - 1):
                if arr[j] > arr[j + 1]:
                    BubbleSort._exchange(arr, j, j + 1)
                    # un_exchanges = False
                    last_swapped_index = j + 1
            # if un_exchanges:
            #     break

            # i 赋值为总数减去有序的数字数量
            i = count - last_swapped_index
            # 如果last_swapped_index == 0 说明都有序 那么i就会 == count 结束循环


    @staticmethod
    def _exchange(arr: list, a: int, b: int):
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp


class ShellSort:
    @staticmethod
    def sort(arr: list):
        # h是比较元素大小的间隔
        h = int(len(arr) / 2)
        while h >= 1:
            # 内部是插入排序
            # arr[h, arr.length)
            for i in range(h, len(arr)):
                t = arr[i]
                j = i
                while j - h >= 0 and t < arr[j - h]:
                    arr[j] = arr[j - h]
                    j -= h
                arr[j] = t

            h = int(h / 2)


if __name__ == '__main__':
    from array_generator import ArrayGenerator

    l1 = ArrayGenerator.generate_random_array(30)
    QuickSort.sort(l1)
    print(l1)
